#include<stdio.h>
#include<stdlib.h>

typedef struct{
  short *arr;
  unsigned short size;
}Array;

void sudokoPrintBoard(short **board)
{

  printf(" | 0 1 2| 3 4 5| 6 7 8\n");
  printf("-----------------------\n");
  for(int i=0;i<9;i++)
  {
    printf("%d|", i);
    for(int j=0;j<9;j++)
      {
        if((*board)[i*9 + j]!=-1) printf(" %d", (*board)[i*9 + j]);
        else printf("  ");
        if((j==2)||(j==5)) printf("|");
      }
    if((i+1)%3==0) printf("\n-----------------------\n");
    else printf("\n");
  }
}

short digitAt(short **board, int x, int y)
{
  return *board[x*9 + 1];
}
void freeOptions(Array ***options)
{
  for (int i = 0; i < 9 ; i++)
    {
      for (int j = 0; j < 9 ; j++)
        {
          if(options[i][j]!=NULL)
            {
              free(options[i][j]->arr);
              free(options[i][j]);
              options[i][j] = NULL;
            }
        }
      free(options[i]);
      options[i] = NULL;

    }
  free(options);
  options = NULL;
}
short *optionsAt(short **board, int x, int y, unsigned short *size)
{
  short *ret = malloc(sizeof(short) * 9);
  int flag;
  for(int j = 1; j<=9; j++)
    {
      flag = 0;
      for (int i = x*9 ; i <(x+1)*9 ; i++) // line check
          if((*board)[i] == j) flag = 1;
      for(int i = y; i< 81; i+=9) // row check
        if((*board)[i] == j) flag = 1;
      for(int i = (x/3 * 3)*9 + (y/3 * 3);i<(x/3 * 3)*9 + (y/3 * 3) + 17;i+=9)
        {
          if(((*board)[i] == j) || ((*board)[i+1] == j)||((*board)[i+2] == j)) flag = 1;
        }
      if(!flag)
        {
          ret[*size] = j;
          (*size)++;
        }
    }

  return ret;
}

Array ***PossibleDigits(short **sudokuBoard)
{
  Array ***ret;
  ret = malloc(sizeof(Array **)* 9);
  for (int i = 0; i < 9 ; i++)
    {
      ret[i] = malloc(sizeof(Array *) * 9);
      for (int j = 0; j < 9 ; j++)
        {
          if((*sudokuBoard)[i*9 + j] != -1)
            ret[i][j]=NULL;
          else
            {
              ret[i][j] = malloc(sizeof(Array));
              ret[i][j]->arr = optionsAt(sudokuBoard, i, j, &ret[i][j]->size);
            }
        }

    }

  return ret;
}

int FillBoard(short **board, Array ***possibilities)
{
  int flag = 1;
  int x, y;
  short sel;
  unsigned short min;
  while(flag)
    {
      flag = 0;
      for (int i = 0; i < 9 ; i++)
        {
          for (int j = 0; j < 9 ; j++)
            {
              if(possibilities[i][j]!= NULL)
                {
                  if(possibilities[i][j]->size == 1)
                    {
                      (*board)[i*9+j] = (possibilities[i][j]->arr)[0];
                      flag = 1;
                    }
                  else if(possibilities[i][j]->size == 0)
                    {
                      return -1;
                    }
                }
            }
        }
      possibilities = PossibleDigits (board);
    }
  min = 10;
   for (int i = 0; i < 9 ; i++)
        {
          for (int j = 0; j < 9 ; j++)
            {
              if(possibilities[i][j] != NULL)
                if(min > possibilities[i][j]->size)
                  {
                    min = possibilities[i][j]->size;
                    x = i;
                    y = j;
                }
            }
        }
  if(min == 10) return 0;
  sudokoPrintBoard (board);
  printf("Cell number [%d,%d] currently holds the minimum number of possible values, select one of the below:\n", x, y);
  for (int i = 0; i <possibilities[x][y]->size ; i++)
    printf("%d. %d\n",i+1, possibilities[x][y]->arr[i]);
  scanf("%hd", &sel);
  printf("Updating cell %d with value %d\n", x*9+y, sel);
  (*board)[x*9 + y] = sel;
  possibilities = PossibleDigits (board);
  return FillBoard (board, possibilities);

  return -1;
}

int main()
{
  short board[81] = {5,-1,4,-1,7,-1,-1,1,-1,6,-1,2,1,-1,-1,3,-1,-1,1,-1,8,-1,4,-1,-1,6,-1,-1,5,-1,-1,6,-1,-1,2,-1,-1,2,-1,8,-1,3,-1,-1,-1,-1,-1,-1,-1,-1,4,-1,5,6,-1,6,1,5,3,7,2,8,4,-1,8,7,-1,1,9,-1,3,-1,-1,-1,-1,2,8,-1,-1,-1,9};
  short * sudoko_board = board;
  Array*** possible_solutions;

  printf("Initial board\n");
  sudokoPrintBoard(&sudoko_board);
  printf("Press enter to start playing...\n");
  getchar();
  possible_solutions = PossibleDigits(&sudoko_board);
  if (FillBoard(&sudoko_board,possible_solutions) == -1)
    printf("User's selections led to duplications\n");
  else
    {
      sudokoPrintBoard(&sudoko_board);
      printf("Board filled successfully\n");
    }
}
